SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Yen's algorithm</title>

</head>

Yen's algorithm

</h1>

</header>

In <a href="Graph_theory" title="Graph theory">graph theory</a>, Yen's algorithm computes single-source <a href="K_shortest_path_routing" title="K shortest path routing">K-shortest</a> loopless paths for a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> with non-negative <a href="Glossary_of_graph_theory#Basics" title="Glossary of graph theory">edge</a> cost.<a href="#cite_note-yenksp-1">[1]</a> The algorithm was published by Jin Y. Yen in 1971 and employs any <a href="Shortest_path_algorithm" class="mw-redirect" title="Shortest path algorithm">shortest path algorithm</a> to find the best path, then proceeds to find K − 1 deviations of the best path.<a href="#cite_note-yenksp2-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Terminology_and_notation">Terminology and notation</h3></div>

<th>Notation</th>

<th>Description

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></td>

<td>The size of the graph, i.e., the number of nodes in the network.

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i)}</annotation>

</semantics>

</math><img src="./2114fa9ad4fe17a7e5e3a23ff1f2852d3fbfd115.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.612ex; height:2.843ex;" alt="{\displaystyle (i)}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th node of the graph, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">. This means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1)}</annotation>

</semantics>

</math><img src="./a25115739469707c4758b189fe310a750092a80a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle (1)}" loading="lazy"> is the source node of the graph, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N)}</annotation>

</semantics>

</math><img src="./1ef1affa0ad7069851b8f0f7cd33359ad049813a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.873ex; height:2.843ex;" alt="{\displaystyle (N)}" loading="lazy"> is the sink node of the graph.

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{ij}}</annotation>

</semantics>

</math><img src="./f8b0116346390c7dcd72d9ed714177a9b6c81e57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.686ex; height:2.843ex;" alt="{\displaystyle d_{ij}}" loading="lazy"></td>

<td>The cost of the edge between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i)}</annotation>

</semantics>

</math><img src="./2114fa9ad4fe17a7e5e3a23ff1f2852d3fbfd115.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.612ex; height:2.843ex;" alt="{\displaystyle (i)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (j)}</annotation>

</semantics>

</math><img src="./001f05a7e729559d7046831934d9d074db521f7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.767ex; height:2.843ex;" alt="{\displaystyle (j)}" loading="lazy">, assuming that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i)\neq (j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i)\neq (j)}</annotation>

</semantics>

</math><img src="./3f9db594ff7cc6ab5fe3298e7efa5976318af7e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.478ex; height:2.843ex;" alt="{\displaystyle (i)\neq (j)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{ij}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{ij}\geq 0}</annotation>

</semantics>

</math><img src="./9a066337db6c86d474ea232bd2a0df8bbbc7aed9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.947ex; height:2.843ex;" alt="{\displaystyle d_{ij}\geq 0}" loading="lazy">.

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-th shortest path from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1)}</annotation>

</semantics>

</math><img src="./a25115739469707c4758b189fe310a750092a80a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle (1)}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N)}</annotation>

</semantics>

</math><img src="./1ef1affa0ad7069851b8f0f7cd33359ad049813a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.873ex; height:2.843ex;" alt="{\displaystyle (N)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">. Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}=(1)-(2^{k})-(3^{k})-\cdots -({Q_{k}}^{k})-(N)}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}=(1)-(2^{k})-(3^{k})-\cdots -({Q_{k}}^{k})-(N)}</annotation>

</semantics>

</math><img src="./24e318e34a4138f088d67e1f2c73d798393f245d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.646ex; height:3.176ex;" alt="{\displaystyle A^{k}=(1)-(2^{k})-(3^{k})-\cdots -({Q_{k}}^{k})-(N)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2^{k})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2^{k})}</annotation>

</semantics>

</math><img src="./e9f4416edc7a42e675247df9b84bb4fdaaa106cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.06ex; height:3.176ex;" alt="{\displaystyle (2^{k})}" loading="lazy"> is the 2nd node of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-th shortest path, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (3^{k})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (3^{k})}</annotation>

</semantics>

</math><img src="./cd189e85b20206487626e0d45a4ecd27804b2b31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.06ex; height:3.176ex;" alt="{\displaystyle (3^{k})}" loading="lazy"> is the 3rd node of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-th shortest path, and so on.

</td></tr>

<tr>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{k}}_{i}}</annotation>

</semantics>

</math><img src="./d7ef6d88b3fdaf5c3e1daac5226424a02fd9a0cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.632ex; height:3.009ex;" alt="{\displaystyle {A^{k}}_{i}}" loading="lazy"></td>

<td>A deviation path from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> at node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i)}</annotation>

</semantics>

</math><img src="./2114fa9ad4fe17a7e5e3a23ff1f2852d3fbfd115.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.612ex; height:2.843ex;" alt="{\displaystyle (i)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{k}}</annotation>

</semantics>

</math><img src="./2fa6cb6cf7ffc157202e52dd5711e755892d1015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.927ex; height:2.509ex;" alt="{\displaystyle Q_{k}}" loading="lazy">. Note that the maximum value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{k}}</annotation>

</semantics>

</math><img src="./2fa6cb6cf7ffc157202e52dd5711e755892d1015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.927ex; height:2.509ex;" alt="{\displaystyle Q_{k}}" loading="lazy">, which is the node just before the sink in the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> shortest path. This means that the deviation path cannot deviate from the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>

</semantics>

</math><img src="./21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy"> shortest path at the sink. The paths <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> follow the same path until the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th node, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i)^{k}-(i+1)^{k}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i)^{k}-(i+1)^{k}}</annotation>

</semantics>

</math><img src="./7524670d9f7c4227e89f39fb41c42729e79d286d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.244ex; height:3.176ex;" alt="{\displaystyle (i)^{k}-(i+1)^{k}}" loading="lazy"> edge is different from any path in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{j}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{j}}</annotation>

</semantics>

</math><img src="./447068b028400a3e454b3b8cd8dd4ba444ab25e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.653ex; height:2.676ex;" alt="{\displaystyle A^{j}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>

</semantics>

</math><img src="./21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy">.

</td></tr>

<tr>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {R^{k}}_{i}}</annotation>

</semantics>

</math><img src="./44837d88ebef69bafe624cfdde800a2bb9e82d14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.652ex; height:3.009ex;" alt="{\displaystyle {R^{k}}_{i}}" loading="lazy"></td>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{k}}_{i}}</annotation>

</semantics>

</math><img src="./d7ef6d88b3fdaf5c3e1daac5226424a02fd9a0cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.632ex; height:3.009ex;" alt="{\displaystyle {A^{k}}_{i}}" loading="lazy"> that follows that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> until the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th node of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy">.

</td></tr>

<tr>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{k}}_{i}}</annotation>

</semantics>

</math><img src="./6747b479b61570082c2c1d0b2b07ecb4b36e5dd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.41ex; height:3.009ex;" alt="{\displaystyle {S^{k}}_{i}}" loading="lazy"></td>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{k}}_{i}}</annotation>

</semantics>

</math><img src="./d7ef6d88b3fdaf5c3e1daac5226424a02fd9a0cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.632ex; height:3.009ex;" alt="{\displaystyle {A^{k}}_{i}}" loading="lazy"> that starts at the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th node of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{k}}_{i}}</annotation>

</semantics>

</math><img src="./d7ef6d88b3fdaf5c3e1daac5226424a02fd9a0cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.632ex; height:3.009ex;" alt="{\displaystyle {A^{k}}_{i}}" loading="lazy"> and ends at the sink.

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Description">Description</h3></div>

The algorithm can be broken down into two parts: determining the first <a href="K_shortest_path_routing" title="K shortest path routing">k-shortest path</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{1}}</annotation>

</semantics>

</math><img src="./2f476475dcf7e8bd1bda0c86caf443e910f5640a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{1}}" loading="lazy">, and then determining all other k-shortest paths. It is assumed that the container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> will hold the k-shortest path, whereas the container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> will hold the potential k-shortest paths. To determine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{1}}</annotation>

</semantics>

</math><img src="./2f476475dcf7e8bd1bda0c86caf443e910f5640a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{1}}" loading="lazy">, the shortest path from the source to the sink, any efficient <a href="Shortest_path_algorithm" class="mw-redirect" title="Shortest path algorithm">shortest path algorithm</a> can be used.

To find the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">, the algorithm assumes that all paths from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{1}}</annotation>

</semantics>

</math><img src="./2f476475dcf7e8bd1bda0c86caf443e910f5640a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{1}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> have previously been found. The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> iteration can be divided into two processes: finding all the deviations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{k}}_{i}}</annotation>

</semantics>

</math><img src="./d7ef6d88b3fdaf5c3e1daac5226424a02fd9a0cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.632ex; height:3.009ex;" alt="{\displaystyle {A^{k}}_{i}}" loading="lazy"> and choosing a minimum length path to become <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy">. Note that in this iteration, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {Q^{k}}_{k}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {Q^{k}}_{k}}</annotation>

</semantics>

</math><img src="./331bad7f8d93f72307ebb300a996013f81313384.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.016ex; height:3.176ex;" alt="{\displaystyle {Q^{k}}_{k}}" loading="lazy">.

The first process can be further subdivided into three operations: choosing the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {R^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {R^{k}}_{i}}</annotation>

</semantics>

</math><img src="./44837d88ebef69bafe624cfdde800a2bb9e82d14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.652ex; height:3.009ex;" alt="{\displaystyle {R^{k}}_{i}}" loading="lazy">, finding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {S^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{k}}_{i}}</annotation>

</semantics>

</math><img src="./6747b479b61570082c2c1d0b2b07ecb4b36e5dd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.41ex; height:3.009ex;" alt="{\displaystyle {S^{k}}_{i}}" loading="lazy">, and then adding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{k}}_{i}}</annotation>

</semantics>

</math><img src="./d7ef6d88b3fdaf5c3e1daac5226424a02fd9a0cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.632ex; height:3.009ex;" alt="{\displaystyle {A^{k}}_{i}}" loading="lazy"> to the container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">. The root path, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {R^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {R^{k}}_{i}}</annotation>

</semantics>

</math><img src="./44837d88ebef69bafe624cfdde800a2bb9e82d14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.652ex; height:3.009ex;" alt="{\displaystyle {R^{k}}_{i}}" loading="lazy">, is chosen by finding the subpath in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> that follows the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> nodes of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{j}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{j}}</annotation>

</semantics>

</math><img src="./447068b028400a3e454b3b8cd8dd4ba444ab25e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.653ex; height:2.676ex;" alt="{\displaystyle A^{j}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>

</semantics>

</math><img src="./21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy">. Then, if a path is found, the cost of edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{i(i+1)}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{i(i+1)}}</annotation>

</semantics>

</math><img src="./3a1d7cd0fc6734590fd78f862f3cf7f55ae29f74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.956ex; height:3.009ex;" alt="{\displaystyle d_{i(i+1)}}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{j}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{j}}</annotation>

</semantics>

</math><img src="./447068b028400a3e454b3b8cd8dd4ba444ab25e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.653ex; height:2.676ex;" alt="{\displaystyle A^{j}}" loading="lazy"> is set to infinity. Next, the spur path, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {S^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{k}}_{i}}</annotation>

</semantics>

</math><img src="./6747b479b61570082c2c1d0b2b07ecb4b36e5dd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.41ex; height:3.009ex;" alt="{\displaystyle {S^{k}}_{i}}" loading="lazy">, is found by computing the shortest path from the spur node, node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, to the sink. The removal of previous used edges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i)}</annotation>

</semantics>

</math><img src="./2114fa9ad4fe17a7e5e3a23ff1f2852d3fbfd115.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.612ex; height:2.843ex;" alt="{\displaystyle (i)}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i+1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i+1)}</annotation>

</semantics>

</math><img src="./01d1bd3a07f06d94e26759b664525a5eb7570e8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.615ex; height:2.843ex;" alt="{\displaystyle (i+1)}" loading="lazy"> ensures that the spur path is different. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{k}}_{i}={R^{k}}_{i}+{S^{k}}_{i}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{k}}_{i}={R^{k}}_{i}+{S^{k}}_{i}}</annotation>

</semantics>

</math><img src="./99c2439068b891b5d311303b36c3a97086e4f697.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.633ex; height:3.009ex;" alt="{\displaystyle {A^{k}}_{i}={R^{k}}_{i}+{S^{k}}_{i}}" loading="lazy">, the addition of the root path and the spur path, is added to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">. Next, the edges that were removed, i.e. had their cost set to infinity, are restored to their initial values.

The second process determines a suitable path for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy"> by finding the path in container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> with the lowest cost. This path is removed from container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> and inserted into container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, and the algorithm continues to the next iteration.

<div class="mw-heading mw-heading3"><h3 id="Pseudocode">Pseudocode</h3></div>

The algorithm assumes that the <a href="Dijkstra_algorithm" class="mw-redirect" title="Dijkstra algorithm">Dijkstra algorithm</a> is used to find the shortest path between two nodes, but any shortest path algorithm can be used in its place.

<pre>function YenKSP(Graph, source, sink, K):

// Determine the shortest path from the source to the sink.

A[0] = Dijkstra(Graph, source, sink);

// Initialize the set to store the potential kth shortest path.

B = [];

for k from 1 to K:

// The spur node ranges from the first node to the next to last node in the previous k-shortest path.

for i from 0 to size(A[k − 1]) − 2:

// Spur node is retrieved from the previous k-shortest path, k − 1.

spurNode = A[k-1].node(i);

// The sequence of nodes from the source to the spur node of the previous k-shortest path.

rootPath = A[k-1].nodes(0, i);

for each path p in A:

if rootPath == p.nodes(0, i):

// Remove the links that are part of the previous shortest paths which share the same root path.

remove p.edge(i,i + 1) from Graph;

for each node rootPathNode in rootPath except spurNode:

remove rootPathNode from Graph;

// Calculate the spur path from the spur node to the sink.

// Consider also checking if any spurPath found

spurPath = Dijkstra(Graph, spurNode, sink);

// Entire path is made up of the root path and spur path.

totalPath = rootPath + spurPath;

// Add the potential k-shortest path to the heap.

if (totalPath not in B):

B.append(totalPath);

// Add back the edges and nodes that were removed from the graph.

restore edges to Graph;

restore nodes in rootPath to Graph;

if B is empty:

// This handles the case of there being no spur paths, or no spur paths left.

// This could happen if the spur paths have already been exhausted (added to A),

// or there are no spur paths at all - such as when both the source and sink vertices

// lie along a "dead end".

break;

// Sort the potential k-shortest paths by cost.

B.sort();

// Add the lowest cost path becomes the k-shortest path.

A[k] = B[0];

// In fact we should rather use shift since we are removing the first element

B.pop();

return A;

</pre>

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

The example uses Yen's K-Shortest Path Algorithm to compute three paths from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C)}</annotation>

</semantics>

</math><img src="./9ebc890748291b3adb437a8c9d086ed466793e11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.576ex; height:2.843ex;" alt="{\displaystyle (C)}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (H)}</annotation>

</semantics>

</math><img src="./e5e2c94cea4ed8c337c3be262701a594f28c66c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.873ex; height:2.843ex;" alt="{\displaystyle (H)}" loading="lazy">. Dijkstra's algorithm is used to calculate the best path from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C)}</annotation>

</semantics>

</math><img src="./9ebc890748291b3adb437a8c9d086ed466793e11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.576ex; height:2.843ex;" alt="{\displaystyle (C)}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (H)}</annotation>

</semantics>

</math><img src="./e5e2c94cea4ed8c337c3be262701a594f28c66c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.873ex; height:2.843ex;" alt="{\displaystyle (H)}" loading="lazy">, which is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C)-(E)-(F)-(H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C)-(E)-(F)-(H)}</annotation>

</semantics>

</math><img src="./53abf3fb4e24749a72ef97e7a434fd436d4ef188.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.105ex; height:2.843ex;" alt="{\displaystyle (C)-(E)-(F)-(H)}" loading="lazy"> with cost 5. This path is appended to container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> and becomes the first k-shortest path, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{1}}</annotation>

</semantics>

</math><img src="./2f476475dcf7e8bd1bda0c86caf443e910f5640a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{1}}" loading="lazy">.

Node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C)}</annotation>

</semantics>

</math><img src="./9ebc890748291b3adb437a8c9d086ed466793e11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.576ex; height:2.843ex;" alt="{\displaystyle (C)}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{1}}</annotation>

</semantics>

</math><img src="./2f476475dcf7e8bd1bda0c86caf443e910f5640a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{1}}" loading="lazy"> becomes the spur node with a root path of itself, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {R^{2}}_{1}=(C)}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {R^{2}}_{1}=(C)}</annotation>

</semantics>

</math><img src="./f7a46a7cadddc25c6706b8632e8260b5a6c2454c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.547ex; height:3.176ex;" alt="{\displaystyle {R^{2}}_{1}=(C)}" loading="lazy">. The edge, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C)-(E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C)-(E)}</annotation>

</semantics>

</math><img src="./423e8979d1b557d89620adf1ef2d56d589e5d36a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.001ex; height:2.843ex;" alt="{\displaystyle (C)-(E)}" loading="lazy">, is removed because it coincides with the root path and a path in container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">. Dijkstra's algorithm is used to compute the spur path <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {S^{2}}_{1}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{2}}_{1}}</annotation>

</semantics>

</math><img src="./33b527dfdf5db3ea199bb23338fc434c8691187d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.63ex; height:3.009ex;" alt="{\displaystyle {S^{2}}_{1}}" loading="lazy">, which is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C)-(D)-(F)-(H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C)-(D)-(F)-(H)}</annotation>

</semantics>

</math><img src="./c5bd874349641bbfae101240d384725189f47e9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.253ex; height:2.843ex;" alt="{\displaystyle (C)-(D)-(F)-(H)}" loading="lazy">, with a cost of 8. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{2}}_{1}={R^{2}}_{1}+{S^{2}}_{1}=(C)-(D)-(F)-(H)}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{2}}_{1}={R^{2}}_{1}+{S^{2}}_{1}=(C)-(D)-(F)-(H)}</annotation>

</semantics>

</math><img src="./5ad7dd63797f2b4ed49c4a3cec170e899610551d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.645ex; height:3.176ex;" alt="{\displaystyle {A^{2}}_{1}={R^{2}}_{1}+{S^{2}}_{1}=(C)-(D)-(F)-(H)}" loading="lazy"> is added to container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> as a potential k-shortest path.

Node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E)}</annotation>

</semantics>

</math><img src="./69ad56f168aab34124adbda79b9164eaacca8373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.585ex; height:2.843ex;" alt="{\displaystyle (E)}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{1}}</annotation>

</semantics>

</math><img src="./2f476475dcf7e8bd1bda0c86caf443e910f5640a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{1}}" loading="lazy"> becomes the spur node with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {R^{2}}_{2}=(C)-(E)}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {R^{2}}_{2}=(C)-(E)}</annotation>

</semantics>

</math><img src="./b68ba4e3f0bc2bd6a81c9ae44f7a939b880e32c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.972ex; height:3.176ex;" alt="{\displaystyle {R^{2}}_{2}=(C)-(E)}" loading="lazy">. The edge, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E)-(F)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E)-(F)}</annotation>

</semantics>

</math><img src="./760f72db974008413a43d1e9bdd836cb6b53301f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.975ex; height:2.843ex;" alt="{\displaystyle (E)-(F)}" loading="lazy">, is removed because it coincides with the root path and a path in container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">. Dijkstra's algorithm is used to compute the spur path <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {S^{2}}_{2}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{2}}_{2}}</annotation>

</semantics>

</math><img src="./29895c117118c4ce9f02976567d3d8dd2367948e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.63ex; height:3.009ex;" alt="{\displaystyle {S^{2}}_{2}}" loading="lazy">, which is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E)-(G)-(H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E)-(G)-(H)}</annotation>

</semantics>

</math><img src="./ceec5c7b68ff9220bdf4c65255cbc3cb49cd1606.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.775ex; height:2.843ex;" alt="{\displaystyle (E)-(G)-(H)}" loading="lazy">, with a cost of 7. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{2}}_{2}={R^{2}}_{2}+{S^{2}}_{2}=(C)-(E)-(G)-(H)}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{2}}_{2}={R^{2}}_{2}+{S^{2}}_{2}=(C)-(E)-(G)-(H)}</annotation>

</semantics>

</math><img src="./44ac084b8bb257fdea31ed3c556f66325eddd90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.582ex; height:3.176ex;" alt="{\displaystyle {A^{2}}_{2}={R^{2}}_{2}+{S^{2}}_{2}=(C)-(E)-(G)-(H)}" loading="lazy"> is added to container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> as a potential k-shortest path.

Node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (F)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (F)}</annotation>

</semantics>

</math><img src="./180d5397d3b3579e792cfc630074cdf7c8bad9d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.55ex; height:2.843ex;" alt="{\displaystyle (F)}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{1}}</annotation>

</semantics>

</math><img src="./2f476475dcf7e8bd1bda0c86caf443e910f5640a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{1}}" loading="lazy"> becomes the spur node with a root path, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {R^{2}}_{3}=(C)-(E)-(F)}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {R^{2}}_{3}=(C)-(E)-(F)}</annotation>

</semantics>

</math><img src="./27e1458106f5491f0ed4ac6164a1842fd27d7ca6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.362ex; height:3.176ex;" alt="{\displaystyle {R^{2}}_{3}=(C)-(E)-(F)}" loading="lazy">. The edge, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (F)-(H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (F)-(H)}</annotation>

</semantics>

</math><img src="./52451625a93b826aa2d91821a66fdc37f993f343.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.263ex; height:2.843ex;" alt="{\displaystyle (F)-(H)}" loading="lazy">, is removed because it coincides with the root path and a path in container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">. Dijkstra's algorithm is used to compute the spur path <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {S^{2}}_{3}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{2}}_{3}}</annotation>

</semantics>

</math><img src="./6da840470afae3be6c7e559c177ce5825cb9e292.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.63ex; height:3.009ex;" alt="{\displaystyle {S^{2}}_{3}}" loading="lazy">, which is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (F)-(G)-(H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (F)-(G)-(H)}</annotation>

</semantics>

</math><img src="./be1d6b085bffab5995a7d4e049b1ce0329148cd4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.74ex; height:2.843ex;" alt="{\displaystyle (F)-(G)-(H)}" loading="lazy">, with a cost of 8. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{2}}_{3}={R^{2}}_{3}+{S^{2}}_{3}=(C)-(E)-(F)-(G)-(H)}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{2}}_{3}={R^{2}}_{3}+{S^{2}}_{3}=(C)-(E)-(F)-(G)-(H)}</annotation>

</semantics>

</math><img src="./7b1a03cb2debbdc6ebd72dd95496cf037b1437cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.973ex; height:3.176ex;" alt="{\displaystyle {A^{2}}_{3}={R^{2}}_{3}+{S^{2}}_{3}=(C)-(E)-(F)-(G)-(H)}" loading="lazy"> is added to container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> as a potential k-shortest path.

Of the three paths in container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {A^{2}}_{2}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {A^{2}}_{2}}</annotation>

</semantics>

</math><img src="./6e92108ec78b1bd04e87d0202f3777e1fd3d2b0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.852ex; height:3.009ex;" alt="{\displaystyle {A^{2}}_{2}}" loading="lazy"> is chosen to become <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{2}}</annotation>

</semantics>

</math><img src="./0a6f30e4c77b5a5e1e49ed2592e144389eade5ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{2}}" loading="lazy"> because it has the lowest cost of 7. This process is continued to the 3rd k-shortest path. However, within this 3rd iteration, note that some spur paths do not exist. And the path that is chosen to become <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{3}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{3}}</annotation>

</semantics>

</math><img src="./5e14d57c5ce0ca1c2537fa7e4eae914657ea1687.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.797ex; height:2.676ex;" alt="{\displaystyle A^{3}}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (C)-(D)-(F)-(H)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (C)-(D)-(F)-(H)}</annotation>

</semantics>

</math><img src="./c5bd874349641bbfae101240d384725189f47e9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.253ex; height:2.843ex;" alt="{\displaystyle (C)-(D)-(F)-(H)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Features">Features</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Space_complexity">Space complexity</h3></div>

To store the edges of the graph, the shortest path list <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, and the potential shortest path list <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N^{2}+KN}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N^{2}+KN}</annotation>

</semantics>

</math><img src="./8dee312e0d72f539123b051d4a3715be4145b9c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.147ex; height:2.843ex;" alt="{\displaystyle N^{2}+KN}" loading="lazy"> memory addresses are required.<a href="#cite_note-yenksp2-2">[2]</a> At worse case, the every node in the graph has an edge to every other node in the graph, thus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N^{2}}</annotation>

</semantics>

</math><img src="./fe131b76af8a2bc86e01b14a7ba843db69c1a164.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.177ex; height:2.676ex;" alt="{\displaystyle N^{2}}" loading="lazy"> addresses are needed. Only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle KN}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KN}</annotation>

</semantics>

</math><img src="./93ca19c0cba5699e8ab58f001e683166a3d663bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.13ex; height:2.176ex;" alt="{\displaystyle KN}" loading="lazy"> addresses are need for both list <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> because at most only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> paths will be stored,<a href="#cite_note-yenksp2-2">[2]</a> where it is possible for each path to have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> nodes.

<div class="mw-heading mw-heading3"><h3 id="Time_complexity">Time complexity</h3></div>

The time complexity of Yen's algorithm is dependent on the shortest path algorithm used in the computation of the spur paths, so the Dijkstra algorithm is assumed. Dijkstra's algorithm has a worse case time complexity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(N^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(N^{2})}</annotation>

</semantics>

</math><img src="./e5d43a3df904fa4d7220f5b86285298aa36d969b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.76ex; height:3.176ex;" alt="{\displaystyle O(N^{2})}" loading="lazy">, but using a Fibonacci heap it becomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(M+N\log N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(M+N\log N)}</annotation>

</semantics>

</math><img src="./36813a9f6f0b6f7446a8aae7c7f16c9f0403c7fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.738ex; height:2.843ex;" alt="{\displaystyle O(M+N\log N)}" loading="lazy">,<a href="#cite_note-dijkstra-3">[3]</a> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is the number of edges in the graph. Since Yen's algorithm makes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Kl}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Kl}</annotation>

</semantics>

</math><img src="./29f129a5bc9f708c3d1fd4b8396f6e5235ccc870.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.759ex; height:2.176ex;" alt="{\displaystyle Kl}" loading="lazy"> calls to the Dijkstra in computing the spur paths, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> is the length of spur paths. In a condensed graph, the expected value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log N)}</annotation>

</semantics>

</math><img src="./14eea297b4387decf341763c39dc038e05744272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.005ex; height:2.843ex;" alt="{\displaystyle O(\log N)}" loading="lazy">, while the worst case is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">.

The time complexity becomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(KN(M+N\log N))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(KN(M+N\log N))}</annotation>

</semantics>

</math><img src="./c49eac5f5faf65222e3659c58c85dbce13936ca9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.677ex; height:2.843ex;" alt="{\displaystyle O(KN(M+N\log N))}" loading="lazy">.<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Improvements">Improvements</h2></div>

Yen's algorithm can be improved by using a heap to store <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">, the set of potential k-shortest paths. Using a heap instead of a list will improve the performance of the algorithm, but not the complexity.<a href="#cite_note-5">[5]</a> One method to slightly decrease complexity is to skip the nodes where there are non-existent spur paths. This case is produced when all the spur paths from a spur node have been used in the previous <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy">. Also, if container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K-k}</annotation>

</semantics>

</math><img src="./aa917fb3f07412524466a55f367479516fbd1cc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.118ex; height:2.343ex;" alt="{\displaystyle K-k}" loading="lazy"> paths of minimum length, in reference to those in container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, then they can be extract and inserted into container <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> since no shorter paths will be found.

<div class="mw-heading mw-heading3"><h3 id="Lawler's_modification">Lawler's modification</h3></div>

<a href="Eugene_Lawler" title="Eugene Lawler">Eugene Lawler</a> proposed a modification to Yen's algorithm in which duplicates path are not calculated as opposed to the original algorithm where they are calculated and then discarded when they are found to be duplicates.<a href="#cite_note-6">[6]</a> These duplicates paths result from calculating spur paths of nodes in the root of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy">. For instance, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy"> deviates from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> at some node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i)}</annotation>

</semantics>

</math><img src="./2114fa9ad4fe17a7e5e3a23ff1f2852d3fbfd115.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.612ex; height:2.843ex;" alt="{\displaystyle (i)}" loading="lazy">. Any spur path, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {S^{k}}_{j}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{k}}_{j}}</annotation>

</semantics>

</math><img src="./26028b3d47505d95f600f17ded218f301e84af93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.52ex; height:3.343ex;" alt="{\displaystyle {S^{k}}_{j}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=0,\ldots ,i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=0,\ldots ,i}</annotation>

</semantics>

</math><img src="./09916d84caecf394a06df9e2559d10cb71aadbd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:11.226ex; height:2.509ex;" alt="{\displaystyle j=0,\ldots ,i}" loading="lazy">, that is calculated will be a duplicate because they have already been calculated during the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>

</semantics>

</math><img src="./21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy"> iteration. Therefore, only spur paths for nodes that were on the spur path of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> must be calculated, i.e. only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {S^{k}}_{h}}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {S^{k}}_{h}}</annotation>

</semantics>

</math><img src="./a762ebdb5dd0730dd0bbdb78bb46e7ba24e83c9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.789ex; height:3.009ex;" alt="{\displaystyle {S^{k}}_{h}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> ranges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i+1)^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i+1)^{k-1}}</annotation>

</semantics>

</math><img src="./2e58964e6ffd5146d66671aea5926f0a2634e2d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.804ex; height:3.176ex;" alt="{\displaystyle (i+1)^{k-1}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (Q_{k})^{k-1}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (Q_{k})^{k-1}}</annotation>

</semantics>

</math><img src="./9d5fc24b7d607fae5dbc2f27616ebcec8d35921b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.926ex; height:3.176ex;" alt="{\displaystyle (Q_{k})^{k-1}}" loading="lazy">. To perform this operation for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k}}</annotation>

</semantics>

</math><img src="./635d375f6533a2afe158ada75a3ebb56d623965d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.832ex; height:2.676ex;" alt="{\displaystyle A^{k}}" loading="lazy">, a record is needed to identify the node where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-1}}</annotation>

</semantics>

</math><img src="./b3f4b9974c2822ba4e58afc74ba5abfb77a34427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-1}}" loading="lazy"> branched from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{k-2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{k-2}}</annotation>

</semantics>

</math><img src="./c018990a6b21b90b1522fe236644c216dd1f02fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.932ex; height:2.676ex;" alt="{\displaystyle A^{k-2}}" loading="lazy">.

<ul><li>Yen's improvement to the <a href="Bellman%E2%80%93Ford_algorithm#Yen.27s_improvement" title="Bellman–Ford algorithm">Bellman–Ford algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFYen1970" class="citation journal cs1">Yen, Jin Y. (1970). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fqam%2F253822">"An algorithm for finding shortest routes from all source nodes to a given destination in general networks"</a>. Quarterly of Applied Mathematics. 27 (4): 526–530. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fqam%2F253822">10.1090/qam/253822</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0253822">0253822</a>.</cite>

</li>

<li id="cite_note-yenksp2-2">^ <a href="#cite_ref-yenksp2_2-0">a</a> <a href="#cite_ref-yenksp2_2-1">b</a> <a href="#cite_ref-yenksp2_2-2">c</a> <cite id="CITEREFYen1971" class="citation journal cs1">Yen, Jin Y. (Jul 1971). "Finding the k Shortest Loopless Paths in a Network". Management Science. 17 (11): 712–716. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmnsc.17.11.712">10.1287/mnsc.17.11.712</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2629312">2629312</a>.</cite>

</li>

<li id="cite_note-dijkstra-3"><a href="#cite_ref-dijkstra_3-0">^</a> <cite id="CITEREFFredmanTarjan1984" class="citation conference cs1"><a href="Michael_Fredman" title="Michael Fredman">Fredman, Michael Lawrence</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. <a href="IEEE" class="mw-redirect" title="IEEE">IEEE</a>. pp. 338–346. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1984.715934">10.1109/SFCS.1984.715934</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFBouillet2007" class="citation book cs1">Bouillet, Eric (2007). Path routing in mesh optical networks. Chichester, England: John Wiley & Sons. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780470032985</bdi>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBranderSinclair" class="citation book cs1">Brander, Andrew William; Sinclair, Mark C. A comparative study of k-shortest path algorithms. Department of Electronic Systems Engineering, University of Essex, 1995.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFLawler1972" class="citation journal cs1">Lawler, EL (1972). "A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem". Management Science. 18 (7): 401–405. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmnsc.18.7.401">10.1287/mnsc.18.7.401</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://thinkingscale.com/k-shortest-paths-cpp-version/">Open Source C++ Implementation</a></li>

<li><a rel="nofollow" class="external text" href="https://trac.cpp.al/trac10/ticket/11838">Open Source C++ Implementation using Boost Graph Library</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Graph_and_tree_traversal_algorithms231" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Graph_and_tree_traversal_algorithms231" style="font-size:114%;margin:0 4em"><a href="Graph_traversal" title="Graph traversal">Graph</a> and <a href="Tree_traversal" title="Tree traversal">tree</a> traversal algorithms</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_traversal" title="Graph traversal">Search</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">α–β pruning</a></li>

<li><a href="Best-first_search" title="Best-first search">Best-first search</a></li>

<li><a href="Beam_search" title="Beam search">Beam search</a></li>

<li><a href="Bidirectional_search" title="Bidirectional search">Bidirectional search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a>

<ul><li><a href="Lexicographic_breadth-first_search" title="Lexicographic breadth-first search">Lexicographic</a></li>

<li><a href="Parallel_breadth-first_search" title="Parallel breadth-first search">Parallel</a></li></ul></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a>

<ul><li><a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">Iterative deepening</a></li></ul></li>

<li><a href="Fringe_search" title="Fringe search">Fringe search</a></li>

<li><a href="Jump_point_search" title="Jump point search">Jump point search</a></li>

<li><a href="Monte_Carlo_tree_search" title="Monte Carlo tree search">Monte Carlo tree search</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a></li>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li>

<li><a href="Johnson's_algorithm" title="Johnson's algorithm">Johnson's</a></li>

<li><a href="Shortest_path_faster_algorithm" class="mw-redirect" title="Shortest path faster algorithm">Shortest path faster</a></li>

</ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka's</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal's</a></li>

<li><a href="Reverse-delete_algorithm" title="Reverse-delete algorithm">Reverse-delete</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="List_of_algorithms#Graph_search" title="List of algorithms">List of graph search algorithms</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-13" href="https://en.wikipedia.org/wiki/?title=Yen's_algorithm&oldid=1290294697">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>